package com.simon.study.algorithm.basic;


import java.util.Arrays;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/19 4:21 下午
 */
public class ComplexSort {

    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 4, 8, 9, 6, 3, 4, 1};
        heapSort(arr);

        System.out.println(Arrays.toString(arr));

        arr = new int[]{2, 5, 4, 1, 4, 8, 9, 6, 3, 4, 1};
        bucketSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            heapAdd(arr, i);
        }

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);

        while (heapSize > 1){
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    public static void heapAdd(int[] arr, int index){
        while (arr[index] > arr[(index-1)/2]){
            swap(arr, index, (index-1)/2);
            index = (index-1)/2;
        }
    }


    public static void heapify(int[] arr, int index, int heapSize){
        int left = (index<<1) + 1;

        while (left < heapSize){
            int target = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 : left;
            target     = arr[index] > arr[target] ? index : target;

            if(target == index){ break; }

            swap(arr, index, target);
            index = target;
            left  = (index<<1) + 1;
        }
    }

    public static void swap(int[] arr, int i, int j){
        if( i == j ){ return; }

        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


    public static void bucketSort(int[] arr){
        int ds = getMaxbits(arr);

        int[] dup = new int[arr.length];

        for(int n=1; n<=ds; n++){
            int[] bucket = new int[10];

            for(int i=0; i < arr.length; i++){
                int dn = getBit(arr[i], n);
                bucket[dn]++;
            }

            for(int i=1; i < bucket.length; i++){
                bucket[i] = bucket[i] + bucket[i-1];
            }

            for(int i = arr.length; i > 0; i--){
                int dn = getBit(arr[i-1], n);
                dup[--bucket[dn]] = arr[i-1];
            }

            for (int i=0; i<arr.length; i++){ arr[i] = dup[i]; }
        }
    }


    public static int getMaxbits(int[] arr){
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            max = arr[max] < arr[i] ? i : max;
        }

        int res = 0, num = arr[max];
        while(num > 0){
            num /= 10;
            res++;
        }

        return res;
    }

    public static int getBit(int num, int i){
        return ((int)(num/Math.pow(10, i-1))) % 10;
    }
}
